package 动态规划;

public class _392_判断子序列 {
    public boolean isSubsequence(String s, String t) {
        if (s == null || t == null) throw new IllegalArgumentException();
        int lens = s.length();
        int lent = t.length();
        if (lent < lens) return false;
        if (lens == 0) return true;

        char[] arrs = s.toCharArray();
        char[] arrt = t.toCharArray();

        boolean[][] dp = new boolean[lens + 1][lent + 1];
        dp[0][0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (i > j) continue;
                if (arrs[i - 1] == arrt[j - 1]) {
                    if (i == 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[lens][lent];
    }
}
